#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdint.h>

#include <semaphore.h>
#include <pthread.h>

#define TIME_DIFF(t1, t2) \
	((t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec))

#define N 1024

int nb_thread;
int board[N+2][N+2];
int num_neigh[N+1][N+1];
sem_t *sem1, *sem2;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int  num_alive, maxloop;
struct timeval t1, t2;


void usage(char * prog)
{
  printf("%s nb_iteration nb_thread\n", prog);
}


void output_board(int board[N+2][N+2], int n, int loop) {
  int i,j;
  //  printf("loop %d\n", loop);

  for (i=1; i<n+1; i++) {
    for (j=1; j<n+1; j++) {
      if (board[i][j])
	putchar('X');
      else
	putchar('.');
    }
    putchar('\n');
    
  }
  sleep(1);
  system("clear");

}

void * parallelise(void * param){
  int numero = (intptr_t)param;


  //debut et fin des indices à parcourir pour le thread courant
  long debut = (N/nb_thread) * numero + 1;
  long fin = (numero == nb_thread-1)?N:debut+(N/nb_thread)-1;

  //indice du thread precedant/suivant dans le tableau de thread
  //(correspond aux threads s'occupant des régions voisines)
  int precedent = (numero == 0)?nb_thread-1:numero-1;
  int suivant = (numero == nb_thread-1)?0:numero+1;
  int loop;
  int i,j;
  int num_alive_local;

  num_alive = 0;

  for (loop = 1; loop <= maxloop; loop++) {
    
    //A chaque tour de boucle, les bordures sont recalculées selon les
    //nouvelles cellules vivantes


    //Copie des 4 coins et des lignes extérieures

    //Le dernier thread recopie ce qu'il vient de calculer pour le thread 0
    if (numero == nb_thread-1) {
      board[0][0] = board[N][N];      //coin supérieur gauche
      board[0][N+1] = board[N][1];    //coin supérieur droit
      for (i = 1; i <= N; i++)
	board[0][i] = board[N][i];    //ligne supérieure
    }  

    //Le thread 0 recopie ce qu'il vient de calculer pour le dernier thread
    if (numero == 0) { 
      board[N+1][0] = board[1][N];    //coin inférieur gauche
      board[N+1][N+1] = board[1][1];  //coin inférieur droit
      for (i = 1; i <= N; i++) 
	board[N+1][i] = board[1][i];  //ligne inférieure
    }  
    
    
    //Copie des colonnes concernées par le thread courant
    for (i = debut; i <= fin; i++) {
      board[i][0] = board[i][N]; 
      board[i][N+1] = board[i][1];
    }


    // Barrière "locale" (voisinage)
    sem_post(&sem1[suivant]);
    sem_post(&sem1[precedent]);
    sem_wait(&sem1[numero]);
    sem_wait(&sem1[numero]);

    //Calcul du nombre de voisins vivants
    for (i = debut; i <= fin; i++) {
      for (j = 1; j <= N; j++) {
	num_neigh[i][j] = board[i][j+1] + board[i][j-1] +
	  board[i+1][j] + board[i-1][j] +
	  board[i+1][j+1] + board[i-1][j-1] +
	  board[i+1][j-1] + board[i-1][j+1];
      }
    }
 
    // Barrière "locale" (voisinage)
    sem_post(&sem2[suivant]);
    sem_post(&sem2[precedent]);
    sem_wait(&sem2[numero]);
    sem_wait(&sem2[numero]);

    //Algo jeu de la vie
    num_alive_local = 0;
    int i, j;
    for (i = debut; i <= fin; i++) {
      for (j = 1; j <= N; j++) {
	if (num_neigh[i][j] < 2 || num_neigh[i][j] > 3) 
	  board[i][j] = 0;
	else
	  if (num_neigh[i][j] == 3)
	    board[i][j] = 1;
	
	if (board[i][j] == 1) {
	  num_alive_local ++;
	}
      }
    }
  }

  pthread_mutex_lock(&mutex);
  num_alive += num_alive_local;
  pthread_mutex_unlock(&mutex);

  return NULL;
}

int main(int argc, char* argv[]) {
  unsigned long time;
  int i,j;

  if (argc != 3){
    usage(argv[0]);
    return EXIT_FAILURE;
  }
  maxloop = atoi(argv[1]);
  nb_thread = atoi(argv[2]);

  sem2 = malloc(nb_thread * sizeof(sem_t));
  sem1 = malloc(nb_thread * sizeof(sem_t));
  pthread_t tid[nb_thread];
  
  //Initialisation cellules vivantes en croix, colonne/ligne du milieu
  for (i = 1; i <= N; i++) {
    for (j = 1; j <= N; j++) {
      if (i == N/2 || j == N/2) {
	board[i][j] = 1;
	num_alive ++;
      }
      else
	board[i][j] = 0;
    }
  }

  gettimeofday(&t1,NULL);

  //Impression de la matrice initiale
  //output_board(board, N, 0);


  //Lancement des threads
  for(i = 0; i < nb_thread; i++){
    sem_init(&sem1[i], 0, 0);
    sem_init(&sem2[i], 0, 0); 
  }

  for(i = 0; i < nb_thread; i++){
    pthread_create(&tid[i], NULL, parallelise, (void*)(intptr_t)i);
  }
  
  for(i = 0; i < nb_thread; i++){
    pthread_join(tid[i], NULL);
  }

#ifdef PRINT_ALIVE
    printf("Nombre de cellules vivantes : %d \n", num_alive);
#endif
    
    
  gettimeofday(&t2,NULL);
  time = TIME_DIFF(t1,t2);
  printf("%.2f\n",(float)time/1000);
  
  //Impression de la matrice finale
  //output_board(board, N, 0);

  free(sem1);
  free(sem2);

  return EXIT_SUCCESS;
}

